from typing import List


class Solution:
    def dfs(self, grid: List[List[str]], i: int, j: int):
        if i >= len(grid) or i < 0:
            return
        if j >= len(grid[0]) or j < 0:
            return
        if grid[i][j] == "0":
            return
        grid[i][j] = "0"
        self.dfs(grid, i - 1, j)
        self.dfs(grid, i + 1, j)
        self.dfs(grid, i, j - 1)
        self.dfs(grid, i, j + 1)

    def numIslands(self, grid: List[List[str]]) -> int:
        row = len(grid)
        col = len(grid[0])
        count = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1":
                    count = count + 1
                    self.dfs(grid, i, j)
        return count
